#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
int t,k;
char s[N];
int cnt[30];
int main(void){
    scanf("%d",&t);
    while(t--){
        scanf("%s",s);
        scanf("%d",&k);
        int r=0;
        memset(cnt,0,sizeof(cnt));
        ll sum=0;
        int len=strlen(s);
        for(int i=0;i<len;i++){
            //满足条件
            if(cnt[s[r]-'a']<=k){
                sum+=r-i;
            }
            else{
                sum+=r-i+1;
            }
            //窗口一直右移直到不满足条件
            while(r<len && cnt[s[r]-'a']<k){
                cnt[s[r++]-'a']++;
                sum++;
            }
            //窗口右移，最左元素删除
            cnt[s[i]-'a']--;
        }
        printf("%lld\n",sum);
    }
    return 0;
}